ยินดีต้อนรับสู่บทเรียนที่ 3 ของ Artificial Intelligence Concepts (PolyU COMP5511)ในบทเรียนนี้ เราจะเปลี่ยนจากการค้นหาเส้นทางของเอเจนต์เดียวไปสู่ การค้นหาแบบแข่งขันซึ่งเอเจนต์ทำงานในสภาพแวดล้อมแบบหลายเอเจนต์ที่มีการแข่งขัน เรายังแนะนำ ปัญหาการหาคำตอบภายใต้ข้อจำกัด (CSPs)ซึ่งเป็นแนวคิดที่เป้าหมายคือการหาสถานะที่ตรงตามเงื่อนไขเฉพาะชุดหนึ่ง แทนที่จะเป็นการหาเส้นทาง
แนวคิดหลัก
- การค้นหาแบบแข่งขัน: มุ่งเน้นไปที่อัลกอริทึมเช่น Minimax และ Alpha-Beta Pruning เพื่อการตัดสินใจอย่างมีเหตุผลในการแข่งขันกับคู่ต่อสู้ที่ฉลาด
- Monte Carlo Tree Search (MCTS): ศึกษาแนวทางการตัดสินใจแบบความน่าจะเป็น ซึ่งเป็นแกนหลักของ AI ในเกมสมัยใหม่อย่าง AlphaGo.
- การแก้ปัญหาภายใต้ข้อจำกัด: จำลองปัญหาด้วยตัวแปร โดเมน และข้อจำกัด โดยแก้ด้วย Backtracking และ Local Search.
การวิเคราะห์ความซับซ้อน
ในสถานการณ์การแข่งขัน ความซับซ้อนของพื้นที่การค้นหามักถูกกำหนดโดยค่าแฟกเตอร์การแตกกิ่งของเกม
คำเตือนเรื่องการเปลี่ยนกระบวนทัศน์
ต่างจากการค้นหาแบบมาตรฐาน (เช่น A* หรือ BFS) ที่สภาพแวดล้อมคงที่ การค้นหาแบบแข่งขัน การค้นหาแบบแข่งขันถือว่าสภาพแวดล้อม (คู่ต่อสู้) พยายามลดโอกาสสำเร็จของคุณอย่างแข็งขัน ใน CSPsลำดับของการกระทำมีความสำคัญน้อยกว่าความถูกต้องของการกำหนดค่าสุดท้าย
รหัสเทียมเชิงแนวคิด: ประเภทของเอเจนต์
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).